package dg;

import java.util.*;

public class Demo1 {
    // 支持度阈值
    private final static int SUPPORT = 3;
    // 置信度阈值
    private final static double CONFIDENCE = 0.8;

    public static void main(String[] args) {
        ArrayList<String> dataList = new ArrayList<>();
        dataList.add("M;O;N;K;E;Y;");
        dataList.add("D;O;N;K;E;Y;");
        dataList.add("M;A;K;E;");
        dataList.add("M;U;C;K;Y;");
        dataList.add("C;O;O;K;I;E;");
//        dataList.add("1;2;5;");
//        dataList.add("2;4;");
//        dataList.add("2;3;");
//        dataList.add("1;2;4;");
//        dataList.add("1;3;");
//        dataList.add("2;3;");
//        dataList.add("1;3;");
//        dataList.add("1;2;3;5;");
//        dataList.add("1;2;3;");

        Demo1 demo1 = new Demo1();
        demo1.apriori(dataList);
    }

    /**
     * apriori 的主运算程序
     *
     * @param dataList
     * @return
     */
    private void apriori(ArrayList<String> dataList) {
        Set<String> itemSet = new HashSet<>();
        Map<String, Integer> itemIdMap = new HashMap<>();
        Map<Integer, String> idItemMap = new HashMap<>();
        List<Integer> itemsList = new ArrayList<>();
        getItemSetAndCreateItemIndex(dataList, itemSet, itemsList, itemIdMap, idItemMap);
        int len = itemSet.size();
        List<List<Integer>> countList = getCountList(len);
        Map<Integer, Integer> frequentMap = new HashMap<>();
        for (int i = 1; i <= len; i++) {
            setFrequentMapAndDelNoFrequentSet(countList.get(i), itemsList, frequentMap);
            if (i < len) {
                delNoFrequentSuperSet(countList.get(i), countList.get(i + 1));
            }
        }

        for (int i = 1; i <= len; i++) {
            for (int j = i + 1; j <= len; j++) {
                createAssociationRule(countList.get(i), countList.get(j), frequentMap, idItemMap);
            }
        }

    }

    /**
     * @param itemList
     * @param nextItemList
     * @param frequentMap
     */
    private void createAssociationRule(List<Integer> itemList, List<Integer> nextItemList, Map<Integer, Integer> frequentMap, Map<Integer, String> idItemMap) {
        if (nextItemList == null || nextItemList.isEmpty()) {
            return;
        }
        for (Integer item : itemList) {
            for (Integer nextItem : nextItemList) {
                Integer value = frequentMap.get(item);
                if ((nextItem & item) == item) {
                    Integer nextValue = frequentMap.get(nextItem);
                    float confidence = nextValue / (float) value;
                    if (value != null && nextValue != null && confidence >= CONFIDENCE) {
                        System.out.println(value + "   " + nextValue);
                        printAssociationRule(item, nextItem, confidence, idItemMap);
                    }
                }

            }
        }
    }

    /**
     * 打印关联规则
     *
     * @param item
     * @param nextItem
     * @param confidence
     * @param idItemMap
     */
    private void printAssociationRule(Integer item, Integer nextItem, float confidence, Map<Integer, String> idItemMap) {
        System.out.println(getItemStr(item, idItemMap) + " => " + getItemStr(nextItem, idItemMap) + " = " + confidence);
        System.out.println();
    }

    private String getItemStr(Integer item, Map<Integer, String> idItemMap) {
        int index = 1;
        StringBuilder sb = new StringBuilder();
        while (item != 0) {
            if ((item & 1) == 1) {
                sb.append(idItemMap.get(index));
            }
            item = item >> 1;
            index++;
        }
        return sb.toString();
    }

    /**
     * 在 k 项集的前提下 删除不满足 k 项集 超级的项集
     *
     * @param itemList
     * @param nextItemList
     */
    private void delNoFrequentSuperSet(List<Integer> itemList, List<Integer> nextItemList) {
        Iterator<Integer> nextItemListIter = nextItemList.iterator();
        while (nextItemListIter.hasNext()) {
            Integer nextItem = nextItemListIter.next();
            int orSum = 0;
            for (Integer item : itemList) {
                if ((nextItem & item) == item) {
                    orSum = orSum | item;
                }
                if (orSum == nextItem) {
                    break;
                }
            }
            if (orSum != nextItem) {
                nextItemListIter.remove();
            }
        }

    }

    /**
     * 设置 物品与数量之间的映射关系，并去掉不满足支持度的项集
     *
     * @param countItems
     * @param itemsList
     * @param frequentMap
     */
    private void setFrequentMapAndDelNoFrequentSet(List<Integer> countItems, List<Integer> itemsList, Map<Integer, Integer> frequentMap) {
        Iterator<Integer> iterator = countItems.iterator();
        while (iterator.hasNext()) {
            int countItem = iterator.next();
            int count = 0;
            for (Integer integer : itemsList) {
                if ((integer & countItem) == countItem) {
                    count++;
                }
            }
            if (count >= SUPPORT) {
                frequentMap.put(countItem, count);
            } else {
                iterator.remove();
            }
        }
    }

    /**
     * 获取整数中 1 的个数数组
     *
     * @param len
     * @return
     */

    private List<List<Integer>> getCountList(int len) {
        List<List<Integer>> countList = new ArrayList<>();
        for (int i = 0; i <= len; i++) {
            countList.add(new ArrayList<>());
        }

        int numCount = (int) Math.pow(2, len) - 1;

        for (int i = 1; i <= numCount; i++) {
            int count = bitCount(i);
            countList.get(count).add(i);
        }

        return countList;
    }

    /**
     * 获取一个整数 二进制 1 的个数
     *
     * @param n
     * @return
     */
    private int bitCount(int n) {
        int c;
        for (c = 0; n != 0; ++c) {
            n &= (n - 1); // 清除最低位的1
        }
        return c;
    }


    /**
     * 获取总清单的无重复货物清单
     * 构建货物ID
     *
     * @param dataList
     * @param itemSet
     * @param itemIdMap
     * @param idItemMap
     */
    private void getItemSetAndCreateItemIndex(ArrayList<String> dataList, Set<String> itemSet,
                                              List<Integer> itemsList, Map<String, Integer> itemIdMap, Map<Integer, String> idItemMap) {
        for (String items : dataList) {
            int length = items.length();
            for (int i = 0; i < length; i++) {
                char ch = items.charAt(i);
                if (ch != ';') {
                    itemSet.add(ch + "");
                }
            }
        }

        int index = 1;
        for (String item : itemSet) {
            itemIdMap.put(item, index);
            idItemMap.put(index, item);
            index++;
        }

        for (String items : dataList) {
            int length = items.length();
            int sum = 0;
            for (int i = 0; i < length; i++) {
                char ch = items.charAt(i);
                if (ch != ';') {
                    Integer id = itemIdMap.get(ch + "");
                    int pow = (int) Math.pow(2, id - 1);
                    if ((sum & pow) != pow) {
                        sum = sum + pow;
                    }
                }
            }
            itemsList.add(sum);
        }

    }
}
